package com.lw.leetcode.hash.c;

import com.lw.test.util.Utils;

import java.util.HashSet;
import java.util.Set;

/**
 * Created with IntelliJ IDEA.
 * c
 * hash
 * 1316. 不同的循环子字符串
 * 滚动hash示例
 *
 * @author liw
 * @version 1.0
 * @date 2023/2/16 9:59
 */
public class DistinctEchoSubstrings {

    public static void main(String[] args) {
        DistinctEchoSubstrings test = new DistinctEchoSubstrings();

        // 3 [bca, abc, cab]
//        String str = "abcabcabc";

        // 2 [e, leetcode]
//        String str = "leetcodeleetcode";

        //
        String str = Utils.getStr(2000, 'a', 'z');

        long l1 = System.currentTimeMillis();
        int i = test.distinctEchoSubstrings(str);
        long l2 = System.currentTimeMillis();
        System.out.println(i);
        System.out.println(l2 - l1);
    }

    public int distinctEchoSubstrings(String text) {
        int length = text.length();
        int[][] arr1 = new int[length][length];
        int[][] arr2 = new int[length][length];
        int m1 = 1000000007;
        int m2 = 1000000009;
        char[] chars = text.toCharArray();
        for (int i = 0; i < length; i++) {
            chars[i] -= 'a';
        }
        for (int i = 0; i < length; i++) {
            arr1[i][i] = chars[i];
            arr2[i][i] = chars[i];
            long item1 = chars[i];
            long item2 = chars[i];
            for (int j = i + 1; j < length; j++) {
                int t = chars[j];
                item1 = ((item1 * 26) + t) % m1;
                item2 = ((item2 * 26) + t) % m2;
                arr1[i][j] = (int) item1;
                arr2[i][j] = (int) item2;
            }
        }
        Set<Long> set = new HashSet<>();
        for (int i = 0; i < length; i++) {
            for (int j = i + 1; j < length; j += 2) {
                int v = ((j - i) >> 1) + i;
                if (arr1[i][v] == arr1[v + 1][j] && arr2[i][v] == arr2[v + 1][j]) {
                    long h = (long) arr1[i][v] * m1 + ((long) arr2[i][v] << 10) + (j - i + 1);
                    set.add(h);
                }
            }
        }
        return set.size();
    }

}
